package 作业;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @param <T>
 */
public class BinaryTree<T extends Comparable<T>> {
    private Node<T> root;
    private int size = 0;

    public BinaryTree() {//构造方法
        this.root = null;
    }

    public BinaryTree(T value) {
        this.root = new Node<>(value);
        size++;
    }

    /**
     * @return int
     */
    public int getSize() {//将树的元素个数返回
        return size;
    }

    /**
     * @return boolean
     */
    public boolean isEmpty() {//树如果为空返回true,如果不为空返回false
        return getSize() == 0;
    }

    /**
     * 该方法用于查找指定元素的前驱或者后继
     *
     * @param value    要查找的元素
     * @param treePSRL 查找元素的前驱,后继或者都要
     */
    public void precursorSubsequent(T value, BinaryTreePSRL treePSRL) {
        if (findElement(value)) {
            switch (treePSRL) {
                case BINARY_TREE_PRECURSOR -> {
                    Node<T> parentElement = null;
                    Node<T> childElement = root;
                    while (childElement.value.compareTo(value) != 0) {
                        if (childElement.value.compareTo(value) > 0) {
                            parentElement = childElement;
                            childElement = childElement.left;
                        } else {
                            parentElement = childElement;
                            childElement = childElement.right;
                        }
                    }
                    if (parentElement == null) {
                        System.out.println("该元素没有前驱");
                    } else {
                        System.out.println("该元素的前驱是:");
                        System.out.println(parentElement.value);
                    }
                }
                case BINARY_TREE_SUBSEQUENT -> {
                    Queue<Node<T>> queue = new LinkedList<>();
                    queue.offer(root);
                    while (!queue.isEmpty() && queue.peek().value.compareTo(value) != 0) {
                        if (queue.peek().value.compareTo(value) > 0) {
                            queue.offer(queue.peek().left);
                        } else {
                            queue.offer(queue.peek().right);
                        }
                        queue.poll();
                    }
                    if (queue.peek().left != null) {
                        queue.offer(queue.peek().left);
                    }
                    if (queue.peek().right != null) {
                        queue.offer(queue.peek().right);
                    }
                    queue.poll();
                    if (queue.isEmpty()) {
                        System.out.println("该元素没有后继");
                    } else {
                        System.out.println("该元素的后继有:");
                        while (!queue.isEmpty()) {
                            System.out.print(queue.poll().value + " ");
                        }
                        System.out.println();
                    }
                }
                case BINARY_TREE_PS -> {
                    precursorSubsequent(value, BinaryTreePSRL.BINARY_TREE_PRECURSOR);
                    precursorSubsequent(value, BinaryTreePSRL.BINARY_TREE_SUBSEQUENT);
                }
                default -> System.out.println("查找类型错误");
            }
        } else {
            System.out.println("找不到该元素");
        }
    }

    /**
     * 该方法用于删除用户指定的元素
     *
     * @param deleteElement 要删除的元素
     * @return 删除成功返回true 删除失败返回false
     */
    public boolean findElementAndDelete(T deleteElement) {//删除元素
//      二叉树为空
        if (isEmpty()) {
//          删除失败，返回false
            return false;
//      二叉树不为空
        } else {
//          要删除的元素是root节点
            if (deleteElement.compareTo(root.value) == 0) {
//              调用deleteRoot()方法
                return deleteRoot();
//          要删除的元素不是root节点
            } else {
                return findElementAndDelete(new Node<>(deleteElement));
            }
        }
    }

    /**
     * deleteRoot()方法用于删除二叉树的root节点
     * <p>
     * 该方法仅会被deleteElement(T deleteElement)方法调用,
     * 如果root节点的left和right都为空,则该方法会接将root=null,
     * 如果root节点的left或right中有一个为空,则该方法会将root=非空的left或right
     * 如果root节点的left和right都存在，则该方法会调用findLeftMaxAndDelete(Node<T> deleteElement)方法,以此来改变root节点的value值
     *
     * @return 删除成功返回true 删除失败返回false
     */
    private boolean deleteRoot() {
        if (root.left == null && root.right == null) {
            root = null;
        } else if (root.left == null || root.right == null) {
            root = Objects.requireNonNullElseGet(root.left, () -> root.right);
        } else {
            root.value = findLeftMaxAndDelete(root.left);
        }
        return true;
    }

    /**
     * findLeftMaxAndDelete(Node<T> deleteElement)方法用于返回deleteElement的left树中最大的值
     *
     * @param deleteElement 要删除的元素
     * @return 返回deleteElement的left树中最大的值
     */
    private T findLeftMaxAndDelete(Node<T> deleteElement) {
//      保存要删除元素的父元素
        Node<T> parentElement = deleteElement;
//      保存要删除的元素
        Node<T> childElement = deleteElement.right;

//      要删除的元素不能为空,且要删除元素的right不能为空
        while (childElement != null && childElement.right != null) {
            parentElement = childElement;
            childElement = childElement.right;
        }

        /*
        if (c.left==null){
            p.right=null;
        }else {
            p.right=c.left;
        }
        */

//        将要删除元素的left赋值给父元素的right
        parentElement.right = childElement.left;
//        返回要删除元素的值
        return childElement.value;
    }

    /**
     * @param deleteElement 要删除的node节点
     * @return 删除成功返回true 删除失败返回false
     */
    private boolean findElementAndDelete(Node<T> deleteElement) {
//      父元素
        Node<T> parentElement = null;
//      子元素
        Node<T> childElement = root;

//        如果子元素不为null
        while (childElement != null) {
//            当子元素大于被删除元素,往left移动
            if (childElement.value.compareTo(deleteElement.value) > 0) {
                parentElement = childElement;
                childElement = childElement.left;
//            当子元素小于被删除元素,往right移动
            } else if (childElement.value.compareTo(deleteElement.value) < 0) {
                parentElement = childElement;
                childElement = childElement.right;
//            找到要被删除的元素
            } else {
//                父元素为空,要删除的节点就是root节点
                if (parentElement == null) {
                    return deleteRoot();
//                调用delete(Node<T> parentElement, Node<T> childElement)方法
//                父元素大于子元素,子元素是父元素的left
                } else if (parentElement.value.compareTo(childElement.value) > 0) {
                    return delete(parentElement, childElement, BinaryTreePSRL.BINARY_TREE_LEFT);
//                父元素小于子元素,子元素是父元素的right
                } else {
                    return delete(parentElement, childElement, BinaryTreePSRL.BINARY_TREE_RIGHT);
                }
            }
        }
//        找不到要删除的元素,删除失败返回false
        return false;
    }

    /**
     * @param parentElement 父元素
     * @param childElement  子元素
     * @param rightOrLeft   找left树最大或right树最小
     * @return 删除成功返回true 删除失败返回false
     */
    private boolean delete(Node<T> parentElement, Node<T> childElement, BinaryTreePSRL rightOrLeft) {
        switch (rightOrLeft) {
            case BINARY_TREE_LEFT -> {
//                如果被删除元素的left和right都为空
                if (childElement.left == null && childElement.right == null) {
                    parentElement.left = null;

//                被删除元素的left和right右一个为空
                } else if (childElement.left == null || childElement.right == null) {
//                    left为空
//                    right为空
                    parentElement.left = Objects.requireNonNullElseGet(childElement.left, () -> childElement.right);
//                被删除元素的left和right都存在
                } else {
                    childElement.value = findLeftMaxAndDelete(childElement.left);
                }
                size--;
                return true;
            }
            case BINARY_TREE_RIGHT -> {
//                如果被删除元素的left和right都为空
                if (childElement.left == null && childElement.right == null) {
                    parentElement.right = null;
                    //被删除元素的left和right右一个为空
                } else if (childElement.left == null || childElement.right == null) {
//                    left为空
//                    right为空
                    parentElement.right = Objects.requireNonNullElseGet(childElement.left, () -> childElement.right);
//                被删除元素的left和right都存在
                } else {
                    childElement.value = findLeftMaxAndDelete(childElement.left);
                }
                size--;
                return true;
            }
            default -> {
                try {
                    throw new Exception("删除的类型错误");
                } catch (Exception e) {
                    e.printStackTrace();
                }
                return false;
            }
        }
    }

    /**
     * 查找元素
     *
     * @param value 用户输入要查找的值
     * @return 有则返回ture没有则返回false
     */
    public boolean findElement(T value) {
        Node<T> findElement = root;
        while (findElement != null) {
            if (findElement.value.compareTo(value) == 0) {
                return true;
            } else if (findElement.value.compareTo(value) > 0) {
                findElement = findElement.left;
            } else {
                findElement = findElement.right;
            }
        }
        return false;
    }

    /**
     * 插入元素
     *
     * @param value 用户输入要插入的值
     * @return 插入成功返回ture，插入失败返回false
     */
    public boolean insertElement(T value) {
        //树为空
        if (isEmpty()) {
            root = new Node<>(value);
            size++;
            return true;
        } else {
            //树不为空
            if (findElement(value)) {
                return false;
            } else {
                size++;
                return insertElement(new Node<>(value), root);
            }
        }
    }

    /**
     * @param node 要插入的node
     * @param now  现在所在的node节点
     * @return 插入成功返回true，插入失败返回false
     */
    private boolean insertElement(Node<T> node, Node<T> now) {
        //当now.value>node.value
        if (now.value.compareTo(node.value) > 0) {
            if (now.left != null) {
                return insertElement(node, now.left);
            } else {
                now.left = node;
                return true;
            }
        } else {
            if (now.right != null) {
                return insertElement(node, now.right);
            } else {
                now.right = node;
                return true;
            }
        }
    }

    /**
     * 前序遍历
     */
    public void preOrderTraversal() {
        preOrderTraversal(root);
    }

    /**
     * @param root 前序遍历开始的节点
     */
    private void preOrderTraversal(Node<T> root) {
        if (root != null) {
            System.out.print(root.value + " ");
            preOrderTraversal(root.left);
            preOrderTraversal(root.right);
        }
    }

    /**
     * 中序遍历
     */
    public void inOrderTraversal() {
        inOrderTraversal(root);
    }

    /**
     * @param root 中序遍历开始的节点
     */
    private void inOrderTraversal(Node<T> root) {
        if (root != null) {
            inOrderTraversal(root.left);
            System.out.print(root.value + " ");
            inOrderTraversal(root.right);
        }
    }

    /**
     * 后序遍历
     */
    public void postOrderTraversal() {
        postOrderTraversal(root);
    }

    /**
     * @param root 后序遍历开始的节点
     */
    private void postOrderTraversal(Node<T> root) {
        if (root != null) {
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            System.out.print(root.value + " ");
        }
    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal() {
        if (root != null) {
            System.out.print(root.value + " ");
            levelOrderTraversal(root);
        }
    }

    /**
     * @param root 层序遍历开始的节点
     */
    private void levelOrderTraversal(Node<T> root) {
        Queue<Node<T>> queue = new LinkedList<>();
        queue.offer(root);
        levelOrderTraversal(Objects.requireNonNull(queue.poll()), queue);
    }

    /**
     * @param root  层序遍历开始的节点
     * @param queue 保存节点的队列
     */
    private void levelOrderTraversal(Node<T> root, Queue<Node<T>> queue) {
        if (root.left != null) {
            queue.offer(root.left);
        }
        if (root.right != null) {
            queue.offer(root.right);
        }
        if (!queue.isEmpty()) {
            System.out.print(queue.element().value + " ");
            levelOrderTraversal(Objects.requireNonNull(queue.poll()), queue);
        }
    }

    /**
     *
     */
    public enum BinaryTreePSRL {
        /*

         */
        BINARY_TREE_PRECURSOR,
        BINARY_TREE_SUBSEQUENT,
        BINARY_TREE_RIGHT,
        BINARY_TREE_LEFT,
        BINARY_TREE_PS
    }

    /**
     * @param <T>
     */
    private static class Node<T extends Comparable<T>> {
        private Node<T> left;
        private Node<T> right;
        private T value;

        private Node(T value) {
            this.left = null;
            this.right = null;
            this.value = value;
        }
    }
}
